package com.test.daily.leetcode.y2022.m05.day0519.v03;

import java.util.HashMap;

/**
 * @descriptions:
 * @author: Tom
 * @date: 2022/5/19 下午 01:30
 * @version: 1.0
 */
public class Solution {
    public static class Node {
        int value;
        Node next;
        Node random;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node copyListWithRandom(Node head) {
        Node cur = head;
        HashMap<Node, Node> map = new HashMap<>();
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        while (cur != null) {
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }

    public static Node copyListWithRandom2(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        // 1. 複製節點並串接起來
        while (cur != null) {
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        cur = head;
        while (cur != null) {
            Node next = cur.next.next;
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }
        Node ans = head.next;
        cur = head;
        while (cur != null) {
            Node next = cur.next.next;
            Node curCopy = cur.next;
            cur.next = next;
            curCopy.next = next == null ? null : next.next;
            cur = next;
        }
        return ans;
    }

    public static Node copy3(Node head){
        if(head == null){
            return null;
        }
        // 1. 生成copy節點
        Node cur = head;
        while(cur != null){
            Node next = cur.next;
            cur.next = new Node(cur.value);
            cur.next.next = next;
            cur = next;
        }
        // 2. 生成Random節點
        cur = head;
        while(cur != null){
            Node next = cur.next.next;
            cur.next.random = cur.random == null? null: cur.random.next;
            cur = next;
        }
        // 3. 斷開所有的連接節點
        Node ans = head.next;
        cur = head;
        while(cur != null){
            Node next = cur.next.next;
            Node curCopy = cur.next;
            curCopy.next = next.next == null ? null: next.next;
            cur.next = next;
            cur = next;
        }
        return ans;
    }
}
